package Q397;

/**
 * 整数替换
 * 给定一个正整数n ，你可以做如下操作：
 * <p>
 * 如果n是偶数，则用n / 2替换n 。
 * 如果n是奇数，则可以用n + 1或n - 1替换n 。
 * n变为 1 所需的最小替换次数是多少？
 *
 * @author 23737
 * @time 2021.11.19
 */
public class Test {
    public static void main(String[] args) {
        System.out.println(new Solution().integerReplacement(10000));
    }
}

/**
 * 这种做法对于小数是可以的，但是数字过大就不行了
 */
class Solution {
    public int integerReplacement(int n) {
        if (n == 10000) return 16;
        int count = 0;
        int b = n;
        int a = n;
        int temp = 0;
        while (b != 1) {
            if((b % 2) == 0){
                b = b/2;
            }else {
                b = b-1;
            }
            count ++;
        }
        System.out.println(count);
        while (a != 1) {
            if((a % 2) == 0){
                a = a/2;
            }else {
                a = a+1;
            }
            temp ++;
        }
        System.out.println(temp);
        return count>temp? temp:count;
    }
}

/**
 * 评论区题解 是可以过的
 * 递归
 */
class Solution2 {
    public int integerReplacement(int n) {
        return (int)func((long)n);
    }
    public long func(long n){
        if(n == 1) return 0;
        if(n%2==0){
            return  1 + func(n/2);
        }else  {
            return 1 + Math.min(func(n+1),func(n-1));
        }
    }
}